The invention is directed to an approach for implementing an improved resequencer, along with related mechanisms and processes.
Almost all types of computing systems use and implement the concept of messages. A message contains information which is sent from a source location or entity to a receiver location or entity. “Message passing” refers to a type of communications used by computing systems to send and exchange messages from sources to destinations.
When messages are sent from a source to a destination, it is possible that the messages may be delivered out of order. This may occur for many different reasons. For example, consider a set of messages to be delivered across the internet. Dynamic routing is often used to select the particular routes and intermediate nodes through which the messages are delivered from the source to the destination. Because of the dynamic nature of the routing, it is quite possible, and even likely, that the different messages within the set of messages are routed through different pathways, which cause the messages to be delivered at different times. As such, an earlier message in a set sequence may be delivered later in time than a later message within the sequence of messages. Multi-threaded processing may also correspond to messages in a stochastic order that are delivered or received.
If the messages are required to be delivered in a particular sequence to a downstream consumer, the easiest solution would be to make sure that they never get out of order in the first place. In effect, the message delivery patterns or the message paths are selected by the message originator or sender to guarantee that that the messages will always be delivered in a particular order.
However, there are many circumstances in which it is not possible to provide this guarantee of ordering for the messages at delivery. For example, a developer of a downstream component may be just a consumer of messages created by upstream components controlled by other parties, and therefore may not be able to affect or have a choice of how the upstream components implement controls for the order of messages. Thus, the need to implement a component that will reorder messages may arise. In the database application space, this is particularly a problem where application semantics require the messages to be delivered in a particular order.
A resequencer is an apparatus that may be used to deliver incoming messages in a user-specified order to the consumer. The user specifies the new order (or the correct sequence) of the incoming messages and the part of the incoming message that is the sequence identifier of the message. Typically, the sequence identifier is the value of a well-known property in the message header. The sequence identifier and the correct sequence are used to decide on the position of the incoming message in the outgoing message stream. The correct sequence could be something as simple as a sequence of consecutive numbers, such as “1, 2, 3 . . . ” However if the sequence identifier is a non-contiguous space, such as time-based values, then deciding on the position of the incoming message in the outgoing stream is a challenge. This invention presents a solution for resequencing messages when the sequence identifier belongs to a non-contiguous space.
An example scenario in which there may be a need to reorder messages is in the implementation of an Enterprise Service Bus (ESB). The enterprise service bus is a relatively recent development in the computing industry, in which the ESB provides a message-based infrastructure for routing and passing messages between applications. The ESB can be used in conjunction with service-oriented architectures (SOA), which are architectures that define applications which provide functionality based upon re-usable services or applications. The SOA therefore allows very complex business functions to be performed based upon the interaction and interplay between multiple applications. The ESB supports SOA by including sufficient messaging and interconnectivity functionality to allow resources and applications to work together across wide networks.
The ESB architecture creates a situation in which there may exist multiple senders and multiple consumers of messages. Particularly relevant for the present application is the fact that the ESB architecture creates a situation in which the message consumer may not have control over the order in which the messages are sent from the message sender to the message consumer. This situation may exist with other types of middleware architectures as well.
Embodiments of the present invention provide an improved approach for implementing and configuring a resequencer that can efficiently and effectively order messages to be delivered to a message consumer. A best efforts resequencing approach is described for determining a set of messages to process in a computing system. The present embodiments are particularly useful to provide message ordering for ESB architectures and systems. Other and additional objects, features, and advantages of the invention are described in the detailed description, figures, and claims.